from collections import deque


class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if grid == []:
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    count += 1
                    self._one_to_two(grid, (i, j))
        return count

    def _one_to_two(self, grid, location):
        # 一个队列用于BFS,searched用于判断是否重复，避免出现死循环
        search_deque = deque()
        search_deque.append(location)
        search_needed = set()
        m = 0
        while search_deque:
            loc = search_deque.popleft()
            i, j = loc
            grid[i][j] = "2"
            search_needed.add((i, j))
            m += 1

            if i < len(grid) - 1:
                if grid[i + 1][j] == "1" and (i + 1, j) not in search_needed:
                    search_needed.add((i, j))
                    search_deque.append((i + 1, j))
            if i > 0:
                if grid[i - 1][j] == '1' and (i - 1, j) not in search_needed:
                    search_needed.add((i - 1, j))
                    search_deque.append((i - 1, j))
            if j < len(grid[0]) - 1:
                if grid[i][j + 1] == "1" and (i, j + 1) not in search_needed:
                    search_needed.add((i, j + 1))
                    search_deque.append((i, j + 1))
            if j > 0:
                if grid[i][j - 1] == '1' and (i, j - 1) not in search_needed:
                    search_needed.add((i, j - 1))
                    search_deque.append((i, j - 1))
        print(m)


if __name__ == '__main__':
    # l = [['1','1','0','0','0'],
    #      ['1','1','0','0','0'],
    #      ['0','0','1','0','0'],
    #      ['1','1','0','0','0']]

    l = [["1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "0", "1", "1"],
         ["0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "0"],
         ["1", "0", "1", "1", "1", "0", "0", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "0", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "0", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1"],
         ["0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "0", "1", "1", "1", "1"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "0", "1", "1"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["0", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1"],
         ["1", "0", "1", "1", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1", "1", "0", "1", "1", "1"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "0"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "0", "0"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
         ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"]]

    s = Solution()
    cnt = s.numIslands(l)
    print(cnt)
